#ifndef __RADIXTREE_HPP__
#define __RADIXTREE_HPP__

#include <exception>
#include <utility>
#include <ostream>
#include <string>
#include <vector>
#include <map>
#include <cstdlib>
#include <fstream>

using namespace std;

template <typename TType>
class RadixTree {
private:
  class Levenshtein {
  private:
    vector< vector<size_t> > D;
    vector<size_t> C;
    const string& key;
    string edg;
    size_t k;

  public:
    Levenshtein(const string& key, size_t _k)
      : C(1), key(key), k(_k)
    {
      D.push_back( vector<size_t>(key.length()+1) );
      for(size_t j = 0; j <= key.length(); ++j)
	D.front()[j] = j;

      C[0] = k;
    }

    const string& getWord() const
    { return edg; }

    const string& getKey() const
    { return key; }
    
    size_t getDist() const 
    { 
      size_t d = D[edg.length()][key.length()];
      if ( d > 0 || C[edg.length()] >= key.length() )
	return d; 
      else return k+1;
    }

    size_t getLastC() const
    {
      return C[edg.length()];
    }

    size_t getMaxK() const
    { return k; }
    
    void remove_suffix(size_t l)
    {
      D.resize(D.size()-l);
      edg.resize(edg.length()-l);
      C.resize(C.size()-l);
    }

    void add_suffix(const string& s)
    {
      size_t fil = edg.length()+1;
      for(size_t i = 1; i <= s.length(); ++i) {
	D.push_back( vector<size_t>(key.length()+1) );
	D.back()[0] = i+edg.length();
      }
      edg += s;

      C.resize(edg.length()+1, 0);
      
      for(size_t i = fil; i <= edg.length(); ++i) {
	for(size_t j = 1; j <= min(C[i-1]+1,key.length()); ++j) {
	  size_t m = D[i][j-1]+1;
	  
	  if ( C[i-1] >= j && D[i-1][j]+1 < m ) 
	    m = D[i-1][j]+1;
	  
	  if ( C[i-1] >= j-1 ) {
	    if (key[j-1] == edg[i-1] && D[i-1][j-1] < m)
	      m = D[i-1][j-1];
	    else if(D[i-1][j-1]+1 < m)
	      m = D[i-1][j-1]+1;
	  }
	  
	  if ( i > 1 && j > 1 && C[i-2] >= j-2 && C[i-1] > j-1 ) {
	    if (key[j-1]==edg[i-2] && key[j-2]==edg[i-1] && 
		D[i-2][j-2]+1 < m)
	      m = D[i-2][j-2]+1;
	  }
	  
	  D[i][j] = m;
	  if ( m <= k ) C[i] = j;
	}

	if ( C[i] == 0 ) break;
      }
    }
  };

  // Abstract node
  class Node {
  public:
    virtual ~Node() {};
    virtual bool isLeaf() const = 0;
    virtual size_t leafs () const = 0;
    virtual size_t nodes () const = 0;
    virtual void dot(ostream& os) const = 0;
  };
  
  // Leaf node
  class TNode : public Node {
  private:
    TType v;
  public:
    TNode (const TType& v) : Node(), v(v) 
    {}

    bool isLeaf() const 
    { return true; }

    const TType& value () const
    { return v; }

    TType& value () 
    { return v; }

    size_t leafs () const
    { return 1; }

    size_t nodes () const
    { return 1; }

    void dot(ostream& os) const 
    {
      os << "node" << hex << (size_t)this << dec << " [shape=doublecircle]" << endl;
    }
  };

  // Internal node
  class INode : public Node {
  private:
    typedef typename map<string,Node*>::iterator ChIt;
    typedef typename map<string,Node*>::const_iterator ChConstIt;
    map<string, Node*> children;
  public:
    ~INode () 
    {
      for(ChIt cit = children.begin(); cit != children.end(); ++cit)
	delete cit->second;
    }
    
    bool isLeaf() const { return false; }
    
    void insert(const string& key, TType& val) 
    {
      if ( key.length() == 0 || children.size() == 0 ) {
	ChIt it = children.find(key);
	if ( it != children.end() ) ((TNode*)it->second)->value() = val;
	else children[key] = new TNode(val);
	return;
      }
      
      for(ChIt cit = children.begin(); cit != children.end(); ++cit) {
	size_t p = 0;
	while ( key[p] == cit->first[p] && 
		p < key.length() && p < cit->first.length() ) p++;
	
	// no common prefix with the current edge
	if ( p == 0 ) continue;
	
	// key = xy, edge = xz
	string x = key.substr(0, p);
	string y = key.substr(p);
	string z = cit->first.substr(p);
	
	if ( cit->second->isLeaf() ) {
	  if ( y.length() > 0 || z.length() > 0 ) {
	    INode * in = new INode;
	    in->children[y] = new TNode(val);
	    in->children[z] = cit->second;
	    children.erase(cit);
	    children[x] = in;
	  } else {
	    ((TNode*)cit->second)->value() = val;
	  }
	} else {
	  if ( z.length() > 0 ) {
	    INode * in = new INode;
	    in->children[y] = new TNode(val);
	    in->children[z] = cit->second;
	    children.erase(cit);
	    children[x] = in;
	  } else {
	    ((INode*)cit->second)->insert(y, val);
	  }
	}

	return;
      }

      // no common prefix to any edge
      children[key] = new TNode(val);
    }

    TNode* exact_lookup(const string& key) const
    {
      if ( children.size() == 0 ) return 0;

      if ( key.length() == 0 ) {
	ChConstIt cit = children.find("");
	if ( cit == children.end() ) return 0;
	else return (TNode*)cit->second;
      }

      for(ChConstIt cit = children.begin(); cit != children.end(); ++cit) {
        size_t p = 0;
        while ( key[p] == cit->first[p] &&
                p < key.length() && p < cit->first.length() ) p++;

	//cout << "Considering \"" << cit->first << "\"..."; 
	
        // no common prefix with the current edge 
        if ( p == 0 ) { /*cout << "NO" << endl;*/ continue; }

	//cout << "YES" << endl;

	// the matching edge drives to a leaf...
	if ( cit->second->isLeaf() ) {
	  if ( p == key.length() && p == cit->first.length() )
	    return (TNode*)cit->second;
	  else
	    return 0;
	}

	// key = xy, edge = xz
	if ( p == cit->first.length() )
	  return ((INode*)cit->second)->exact_lookup(key.substr(p));
      }
      
      // no common prefix to any edge
      return 0;
    }

    void approximate_lookup(Levenshtein& DL, vector< pair<TType, string> >& result) const
    {
      for(ChConstIt cit = children.begin(); cit != children.end(); ++cit) {
	DL.add_suffix(cit->first);
	if ( cit->second->isLeaf() && DL.getDist() <= DL.getMaxK() ) {
	  pair<TType, string> p(((TNode*)(cit->second))->value(), DL.getWord());
	  result.push_back(p);
	} else if ( !cit->second->isLeaf() && DL.getLastC() > 0 ) {
	  ((INode*)cit->second)->approximate_lookup(DL, result);
	}
	DL.remove_suffix(cit->first.length());
      }
    } 

    size_t leafs () const
    {
      size_t leafs = 0;
      for(ChConstIt cit = children.begin(); cit != children.end(); ++cit)
	leafs += cit->second->leafs();
      return leafs;
    }

    size_t nodes () const
    {
      size_t nodes = 1;
      for(ChConstIt cit = children.begin(); cit != children.end(); ++cit)
	nodes += cit->second->nodes();
      return nodes;
    }

    static string plabel(string s) 
    {
      string ns;
      for(size_t p = 0; p < s.length(); ++p)
	if ( s[p] == '"' ) ns += "\\\"";
	else ns += s[p];
      return ns;
    }

    void dot(ostream& os) const 
    {
      for(ChConstIt cit = children.begin(); cit != children.end(); ++cit) {
	os << "node" << hex << (size_t)this << "->" 
	   << "node" << (size_t)cit->second << dec
	   << " [label=\"" << plabel(cit->first) << "\"]" << endl;
      }
      
      for(ChConstIt cit = children.begin(); cit != children.end(); ++cit) 
	cit->second->dot(os);
    }
  };
  
  INode root;
  size_t count;
public:
  RadixTree() {
    count = 1;
  }
  
  // Exception thrown when a exact lookup fails
  class NoExactResultsException : public exception {
  public:
    virtual const char * what() const throw()
    {
      return "No exact results found";
    }
  };

  void insert(const string& key, TType& val)
  {
    root.insert(key, val);
    /*    char fname[50];
    sprintf(fname, "graph_%lu.dot", count);
    ofstream f; f.open(fname);
    dot(f);
    f.close();
    count++;*/
  }

  pair<bool, TType> exact_lookup(const string&key ) const
  {
    TNode * res = root.exact_lookup(key);
    if ( res == NULL ) return pair<bool,TType>(false, TType());
    else return pair<bool,TType>(true, res->value());
  }
   
  vector< pair<TType, string> > 
  approximate_lookup(const string& key, size_t k) const
  {
    vector< pair<TType, string> > result;
    Levenshtein DL(key, k);
    root.approximate_lookup(DL, result);
    return result;
  } 

  size_t leafs () const
  { return root.leafs(); }

  size_t nodes () const
  { return root.nodes(); }

  void dot(ostream& os) const
  {
    os << "strict digraph {" << endl;
    os << "node [shape=circle,label=\"\"]" << endl;
    os << "edge [labelfloat=false]" << endl;
    os << "graph [forcelabels=true]" << endl;
    root.dot(os);
    os << "}" << endl;
  }
};

#endif
